package 另一棵树的子树;

public class Solution2 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 递归法 TODO
        // ① 参数：左子树，subRoot 返回值：boolean
        // ② 终止条件：root==null&&subRoot==null 或者 root==null||subRoot==null||root.val!=subRoot.val
        // ③ 单层递归的逻辑：以root树的根节点，左节点，右节点当作新树的根节点不断的去和subRoot进行树的匹配
        // 相当于要实现两个递归函数：
        // 其一完成root树的根节点，左节点，右节点当作新树的根节点
        // 其二完成和subRoot进行树的匹配
        if (subRoot == null)
            return true;
        return dfs(root, subRoot);
    }

    // 其一完成root树的根节点，左节点，右节点当作新树的根节点
    public boolean dfs(TreeNode newRoot, TreeNode subRoot) {
        if (newRoot == null)
            return false;
        return check(newRoot, subRoot) || dfs(newRoot.left, subRoot) || dfs(newRoot.right, subRoot);
    }

    // 其二完成和subRoot进行树的匹配
    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        if (p == null || q == null || p.val != q.val)
            return false;
        boolean outer = check(p.left, q.left);
        boolean inner = check(p.right, q.right);
        return outer && inner;
    }
}
